﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Reflector.Graph.Graphs;
using System.IO;
using QuickGraph.Concepts.Collections;
using Reflector.CodeModel;

namespace MethodSeqGenerator
{
    /*
     *Class that primarily accepts a graph and analyzes the graph such as 
     *depth first traversal
     */ 
    class GraphAnalyzer
    {
        StreamWriter sw = null;
        StatementGraph graph = null;

        public GraphAnalyzer(StatementGraph graph)
        {            
            this.graph = graph;
        }

        ~GraphAnalyzer()
        {            
        }

        public void GetBackwardPath(List<MethodInvocationHolder> linearPath, StatementVertex svObj, StatementVertex root, String searchString)
        {
            bool bFirstVertex = true;       //First vertex needs to be dealt separately 
            //as the required method invocation might be somwhere else
            HashSet<StatementVertex> visitedVertices = new HashSet<StatementVertex>();
            while (svObj != root)
            {
                if (visitedVertices.Contains(svObj))
                {
                    break;
                }
                visitedVertices.Add(svObj);

                if (svObj.associatedMIList != null && svObj.associatedMIList.Count > 0)
                {
                    svObj.associatedMIList.Reverse();
                    if (!bFirstVertex)
                    {
                        foreach (MethodInvocationHolder mihObj in svObj.associatedMIList)
                        {
                            linearPath.Add(mihObj);
                        }
                    }
                    else
                    {
                        //In our current implementation, we annonate statement nodes with the 
                        //method invocations. Therefore, sometimes the last node is not the one
                        //we are looking for. The additional implementation helps to make sure that 
                        //the last method invocation is always the one we require
                        bool bAddToList = false;
                        foreach (MethodInvocationHolder mihObj in svObj.associatedMIList)
                        {
                            if (mihObj.returnType.getTypeName().Contains(searchString))
                            {
                                bAddToList = true;
                            }

                            if (bAddToList)
                                linearPath.Add(mihObj);
                        }
                        bFirstVertex = false;
                    }

                    //Resetting back to normal order for traversing in future
                    svObj.associatedMIList.Reverse();

                    if (linearPath.Count > 100)
                    {
                        //A bug in the current reflector that it makes the same node for
                        //statements like "index=0" even if they appear in same places.
                        //Currently this is handled via the number of method invocations
                        //added to linearPath.
                        //SeqGenerator.swLogging.WriteLine("Potential OUT OF MEMORY:" + "DLLName: " +
                        //    SeqGenerator.currentDLL + ", Class: " + SeqGenerator.currentTypeDeclarationName 
                        //    + ", Method: " + SeqGenerator.currentMethodName);                        
                        return;
                    }
                }

                IEdgeCollection inEdgeCollection = this.graph.InEdges(svObj);
                //Select an edge for going back to the root
                int edgeCount = 0;
                int collectionSize = inEdgeCollection.Count;

                if (collectionSize == 0)
                {
                    //There are no incoming edges for the collection
                    break;
                }

                while (true)
                {
                    if (edgeCount == collectionSize)
                    {
                        break;
                    }

                    StatementEdge edge = inEdgeCollection[edgeCount] as StatementEdge;
                    if (edge.Name.Equals("iterate") || edge.Name.Equals("break") || edge.Name.Equals("continue"))
                    {
                        edgeCount++;
                        continue;
                    }

                    break;
                }

                svObj = inEdgeCollection[edgeCount].Source as StatementVertex;
            }
            //End of the code section that needs to be replaced later
        }

        //In forward path, we check for the common receiver object or arguments.
        public void GetForwardPath(List<MethodInvocationHolder> linearPath, StatementVertex svObj, String searchString)
        {
            bool bFirstVertex = true;       //First vertex needs to be dealt separately 
                                            //as the required method invocation might be somwhere else

            HashSet<StatementVertex> visitedVertices = new HashSet<StatementVertex>();
            while (svObj != null)
            {
                visitedVertices.Add(svObj);                
                if (svObj.associatedMIList != null && svObj.associatedMIList.Count > 0)
                {
                    if (!bFirstVertex)
                    {
                        foreach (MethodInvocationHolder mihObj in svObj.associatedMIList)
                        {
                            linearPath.Add(mihObj);
                        }
                    }
                    else
                    {
                        //In our current implementation, we annonate statement nodes with the 
                        //method invocations. Therefore, sometimes the last node is not the one
                        //we are looking for. The additional implementation helps to make sure that 
                        //the last method invocation is always the one we require
                        bool bAddToList = false;
                        foreach (MethodInvocationHolder mihObj in svObj.associatedMIList)
                        {
                            if (mihObj.returnType.getTypeName().Contains(searchString))
                            {
                                bAddToList = true;
                            }

                            if (bAddToList)
                                linearPath.Add(mihObj);
                        }
                        bFirstVertex = false;
                    }

                    //A workaround for time being to prevent OUTOFMEMORY. Because none of the sequences
                    //can have more than 100 method calls.
                    if (linearPath.Count > 100)
                    {
                        //A bug in the current reflector that it makes the same node for
                        //statements like "index=0" even if they appear in same places.
                        //Currently this is handled via the number of method invocations
                        //added to linearPath.
                        //SeqGenerator.swLogging.WriteLine("Potential OUT OF MEMORY:" + "DLLName: " +
                        //    SeqGenerator.currentDLL + ", Class: " + SeqGenerator.currentTypeDeclarationName
                        //    + ", Method: " + SeqGenerator.currentMethodName);
                        return;
                    }
                }

                IEdgeCollection outEdgeCollection = this.graph.OutEdges(svObj);
                //Select an edge for going back to the root
                
                int collectionSize = outEdgeCollection.Count;
                if (collectionSize == 0)
                {
                    //There are no outgoing edges for the collection
                    break;
                }
                
                StatementEdge edge = outEdgeCollection[0] as StatementEdge;
                StatementVertex escapeEdgeTarget = null;
                bool bExitLoop = false;
                if (edge.Name.Equals("iterate") || edge.Name.Equals("continue"))
                {
                    StatementVertex beginBlock = edge.Target as StatementVertex;
                    if (!visitedVertices.Contains(beginBlock))
                    {
                        escapeEdgeTarget = beginBlock;
                    }
                    else
                    {
                        //Choose an outgoing edge from this block that is not existing
                        //in the begin block
                        IEdgeCollection beginOutEdgeCollection = this.graph.OutEdges(beginBlock);
                        foreach (StatementEdge outEdges in beginOutEdgeCollection)
                        {
                            if (!visitedVertices.Contains(outEdges.Target))
                            {
                                escapeEdgeTarget = outEdges.Target;
                                break;
                            }
                        }

                        if (escapeEdgeTarget == null)
                        {
                            //Failed to find the exit. Some problem with the graph 
                            //built by the Graph plugin.
                            bExitLoop = true;
                            break;
                        }
                    }   
                }

                if (escapeEdgeTarget != null)
                {
                    svObj = escapeEdgeTarget;
                }
                else
                {
                    svObj = edge.Target as StatementVertex;
                }
            }
            //End of the code section that needs to be replaced later
        }

        public void ExtractSequence(IStatement graphNode, String searchString)
        {
            //Getting source and destination
            StatementVertex svObj = this.graph.GetVertex(graphNode);
            StatementVertex root = this.graph.Root;
                                            
            //Getting a path from current node to the root. 
            //TODO: Later replace this path with the Dijkstra's shortest path algorithm
            //TODO: Need to figure out how to deal with loops as this may affect 
            //the path computations.
            //List<MethodInvocationHolder> linearBackwardPath = new List<MethodInvocationHolder>();
            //GetBackwardPath(linearBackwardPath, svObj, root, searchString);
            //linearBackwardPath = CaptureMinimalSequenceBackward(linearBackwardPath);
            
            //Gathering linear forward path
            List<MethodInvocationHolder> linearForwardPath = new List<MethodInvocationHolder>();
            GetForwardPath(linearForwardPath, svObj, searchString);
            linearForwardPath = CaptureMinimalSequenceForward(linearForwardPath, searchString);
            if (linearForwardPath.Count() == 0)
                return;

            //Adding the linearPath to the sequence store
            SequenceGroup existingSGObj = (SequenceGroup) SeqGenerator.centralSequenceStore[searchString];
            if (existingSGObj == null)
            {
                existingSGObj = new SequenceGroup();
                SeqGenerator.centralSequenceStore.Add(searchString, existingSGObj);
            }

            bool includeConstructor = true;
            String firstRefName = linearForwardPath[0].referenceClsName.getTypeName();
            if (firstRefName.Contains("UNKNOWN") || firstRefName.Equals("self"))
                includeConstructor = false;

            //If the first method call does not produce an instance of required type and
            //does not include any other method call, it is of no use to us.
            if (!includeConstructor && linearForwardPath.Count() == 1)
                return;

            existingSGObj.AddToSequenceGroup(linearForwardPath, includeConstructor);            
        }

        /*
         * Function that accepts a method invocation holder and adds its all references
         * to the list parameters, especially used for the backward traversal.
         * "UNKNOWN" should never be added to the typeSet
         */ 
        private void addToTypeSet(MethodInvocationHolder mihObj, HashSet<String> typeSet)
        {
            if (!mihObj.methodName.Equals("CONSTRUCTOR") && !mihObj.referenceClsName.getTypeName().Equals("UNKNOWN")
                && !mihObj.referenceClsName.getTypeName().Equals("self")  && !mihObj.bStatic)
            {
                typeSet.Add(mihObj.referenceClsName.getTypeName());
            }            
            foreach (TypeHolder argTyp in mihObj.argStringAr)
            {
                if (!argTyp.getTypeName().Equals("UNKNOWN") && 
                    !argTyp.getTypeName().Equals("self") && 
                    !SeqGenUtil.IsPrimitiveType(argTyp.getTypeName()))
                {
                    typeSet.Add(argTyp.getTypeName());        
                }
            }
        }

        public List<MethodInvocationHolder> CaptureMinimalSequenceForward(List<MethodInvocationHolder> linearPath, String searchString)
        {
            List<MethodInvocationHolder> minimalPath = new List<MethodInvocationHolder>();
            MethodInvocationHolder firstMIH = linearPath[0];
            minimalPath.Add(firstMIH);

            HashSet<String> typeSet = new HashSet<String>();    //Computes the possible new types encountered
                                                                //while minimizing the sequence

            addToTypeSet(firstMIH, typeSet);
            String referenceType = firstMIH.returnType.getTypeName();

            if (!referenceType.Equals(searchString))    //If the first method invocation does not return required
                return minimalPath;                     //type, this sequence is of no use

            String referenceVar = firstMIH.returnType.getVarName(); //If reference variable exists use this variable
                                                                    //for filtering. If not use the entire type for resolution
            
            bool bUseVarComparison = false;
            if (!referenceVar.Equals("") && !referenceVar.Contains("Contains"))
                bUseVarComparison = true;

            //Get the path till the variable is redefined in the path
            int size = linearPath.Count;
            for (int count = 1; count < size; count++)
            {
                MethodInvocationHolder mihObj = linearPath[count];
                bool bMihObjRelated = false;

                if(bUseVarComparison)
                {
                    if (referenceVar.Equals(mihObj.referenceClsName.getVarName()))
                        bMihObjRelated = true;

                    if (referenceVar.Equals(mihObj.returnType.getVarName()))
                        break;          //Variable redefined. So quitting here
                }
                else
                {
                    if(referenceType.Equals(mihObj.referenceClsName.getTypeName()))
                        bMihObjRelated = true;

                    if (referenceType.Equals(mihObj.returnType.getTypeName()))
                        break;         //Variable type re-defined. This may not be safe as the return type
                                       //might be assigned to a new variable.
                }    

                if(bMihObjRelated)
                {
                    minimalPath.Add(mihObj);
                    addToTypeSet(mihObj, typeSet);
                }
                
                //Check whether this reference type is being passed as an argument for
                //any other method. The reason for adding this part is that sometimes, 
                //state of the object can be modified by methods of other class.
                /*else
                {
                    //Check whether any of the arguments are of the referenceType
                    foreach (TypeHolder argTyp in mihObj.argStringAr)
                    {
                        if (argTyp.getTypeName().Equals(referenceType))
                        {
                            minimalPath.Add(mihObj);
                            break;
                        }
                    }
                }*/
            }

            //The elements that remain in typeSet are unknown types
            foreach (String typeElem in typeSet)
            {
                if (typeElem.Contains("UNKNOWN") || typeElem.Equals("self") || SeqGenerator.alreadySearchedStringList.Contains(typeElem))
                    continue;                
                SeqGenerator.newSearchStrings.Add(typeElem);
            }

            return minimalPath;
        }

        public List<MethodInvocationHolder> CaptureMinimalSequenceBackward(List<MethodInvocationHolder> linearPath)
        {
            List<MethodInvocationHolder> minimalPath = new List<MethodInvocationHolder>();
            HashSet<String> typeSet = new HashSet<String>();    //Preserves the types while 
                                                                //traversing backwards
            MethodInvocationHolder firstMIH = linearPath[0];
            minimalPath.Add(firstMIH);
            addToTypeSet(firstMIH, typeSet);
            if (typeSet.Contains(firstMIH.returnType.getTypeName()))
            {
                typeSet.Remove(firstMIH.returnType.getTypeName());
            }

            for (int count = 1; count < linearPath.Count; count ++)
            {
                MethodInvocationHolder mihObj = linearPath[count];
                bool bTypeSetContains = false;
                if (typeSet.Contains(mihObj.returnType.getTypeName()))
                {
                    bTypeSetContains = true;
                    typeSet.Remove(mihObj.returnType.getTypeName());
                }

                if (typeSet.Contains(mihObj.referenceClsName.getTypeName()))
                {
                    bTypeSetContains = true;
                }

                if (bTypeSetContains)
                {
                    minimalPath.Add(mihObj);
                    addToTypeSet(mihObj, typeSet);                
                }
            }
            minimalPath.Reverse();

            //The elements that remain in typeSet are unknown types
            foreach (String typeElem in typeSet)
            {
                if (typeElem.Contains("UNKNOWN") || typeElem.Equals("self") || SeqGenerator.alreadySearchedStringList.Contains(typeElem))
                {
                    continue;
                }
                SeqGenerator.newSearchStrings.Add(typeElem);                
            }
            return minimalPath;
        }

        public void DepthFirstTraversal(StatementVertex vertexNode, IMethodDeclaration methodDeclaration)
        {
            FileStream file = new FileStream(methodDeclaration.Name + ".txt", FileMode.Create, FileAccess.Write);
            sw = new StreamWriter(file);
            HashSet<StatementVertex> visitedVertices = new HashSet<StatementVertex>();
            DepthFirstTraversalLocal(vertexNode, visitedVertices);
            sw.Close();
        }

        //Doing a depth first traversal.
        private void DepthFirstTraversalLocal(StatementVertex vertexNode, HashSet<StatementVertex> visitedVertices)
        {
            if (visitedVertices.Contains(vertexNode))
            {
                return;
            }
            visitedVertices.Add(vertexNode);

            sw.WriteLine(vertexNode.ToString());
            IEdgeCollection iecObj = graph.OutEdges(vertexNode);
            if (iecObj != null && iecObj.Count > 0)
            {
                foreach (StatementEdge seObj in iecObj)
                {
                    StatementVertex outVertex = seObj.Target;
                    DepthFirstTraversalLocal(outVertex, visitedVertices);
                }
            }
        }
    }
}
